Angryk, “Cluster analysis for optimal indexing

High-dimensional indexing is an important area of current re-search, especially for range and kNN queries. This work in-troduces clustering for the sake of indexing. The goal is to de-velop new clustering methods designed to optimize the data partitioning for an indexing-specific tree structure instead of finding data distribution-based clusters. We focus on iDis-tance, a state-of-the-art high-dimensional indexing method, and take a basic approach to solving this new problem. By uti-lizing spherical clusters in an unsupervised Expectation Max-imization algorithm dependent upon local density and cluster overlap, we create a partitioning of the space providing bal-anced segmentation for a B+-tree. We also look at the novel idea of reclustering for a specific indexing method by taking the output of one clustering method and reclustering it fo